\section{Modified acceptance-rejection}
In this problem $\brackk{X_i}$ is a sequence of empirical samples with a possibly unknown density function $f$ with $f\paren{x}=0$ for $\lvert x\rvert>B$.\\

\noindent
We are interested in studying the probability that $\brackk{X_i}$ takes on unusually lage values, and the this should be done by using a version of the "acceptance-rejection" technique. We simulate $U_1,U_2,\ldots,U_n\sim \textrm{Unif(0,1)}$ and accept a given $X_i$ if 
$$
U_i\le e^{\theta(X_i-B)},
$$
and reject $X_i$ otherwise. Let $\brackk{Y_i}$ denote the sequence accepted samples, and $g$ denote the density function of $Y_i$.

\subsection{Determine the density function $g$}
We begin by noticing that since $g$ is the density of the accepted samples $\{Y_i\}$ and $f$ is the density of the empirical samples $\{X_i\}$, and we accept the empirical sample if $U_i\le e^{\theta(X_i-B)}$, then the following relationship holds
$$
g(x)/cf(x) = e^{\theta(x-B)}.
$$

\noindent
$g$ is then given by $g\paren{x} = e^{\theta\paren{x-B}}cf\paren{x} = \tilde{c}e^{\theta x}f\paren{x}$, where $\tilde{c} = \frac{c}{e^{\theta B}}$. Since $g$ is a density we know that it integrates to 1, and we can use this property to find an expression for $\tilde{c}$.

\begin{eqnarray*}
1 &=& \int_{-\infty}^\infty g(x)dx \\
  &=& \tilde{c} \int_{-\infty}^\infty e^{\theta x}f(x) dx,
\end{eqnarray*}

\noindent
which implies that $\frac{1}{\tilde{c}} = \int_{-\infty}^\infty e^{\theta x}f\paren{x} dx$. We can now calculate this integral by change of variable, $y=e^{\theta x}$, which gives $\frac{1}{\theta}dy=e^{\theta x}dx$. Plugging this into the integral and using that $f$ integrates to 1 since it is a density gives us that $\frac{1}{\tilde{c}} = \frac{1}{\theta}$ i.e. $\tilde{c} = \theta$.\\

\noindent
This results in the accepted samples having the density

$$
g(x)=\theta e^{\theta x}f(x).
$$

\subsection{Perform acceptance-rejection procedure}
We now assume that $\{X_i\}$ is an iid. sequence having a Unif(-1,1) distribution and with $\theta=1$ and $\theta = 10$ we perform the acceptance-rejection procedure described in algorithm~\vref{Problem3Algo}.\\

\begin{algorithm}
\caption{Generate a random variable with density g}
\label{Problem3Algo}
\begin{algorithmic}[1]
  \STATE $\theta \leftarrow 1$ or $10$
  \REPEAT
  \STATE Generate $x$ $\sim$ Unif(-1, 1)
  \STATE Generate $u$ $\sim$ Unif(0, 1)
  \UNTIL{$u\le e^{\theta(x-1)}$}
  \RETURN $x$
\end{algorithmic}
\end{algorithm}

\noindent
This algorithm is implemented in \texttt{R} in appendix \ref{code3}. This code produces the following histograms

\begin{center}
\includegraphics[width=10cm]{problem3_1.eps}	   
\end{center}

\noindent
where one can see that $\theta = 10$ produces values closer to 1 compared to $\theta = 1$.\\

\noindent
This also shows in the number of samples accepted by the procedure. For $\lambda=1$, 43\% of the simulated $X_i$'s are accepted, while only 5\% of the values are accepted for $\lambda=10$.\\

\noindent
In the case where $\lambda=1$ the sample mean of the accepted sample is 0.3020735 while the rejected values have mean -0.236943. These values are 0.8996494 for the accepted and -0.04896718 for the rejected in the case where $\lambda=10$.
\newpage
